The present invention relates to data processing systems, and more particularly to controlling access to resources available to such systems.
Multiprocessing computer systems are commonplace. Where more than one process operates concurrently and has access to the same piece of shared data or resource, it is important that access restrictions are employed to ensure the integrity of that data. It is essential that valid data is always read and that updates to the data are correctly recorded. Without careful control, this could quite easily not be the case. If, for example, a process A is reading a bank account total in order to perform some arbitrary calculation, at the same time that a process B is updating the account total, then the calculation will most likely be performed using the old total and will therefore be incorrect. This is simply not acceptable.
It is common, therefore, to use locks to control access to a shared resource. A lock is typically allocated in either shared or exclusive mode. A process, in possession of a shared lock (e.g. a reader), may access the resource for which it holds the lock, alongside other processes also in possession of the shared lock. In other words, multiple readers may access the resource concurrently. When however a writing process (a writer) wishes to access the same resource, no other process must be accessing the data. The writer must therefore obtain an exclusive lock on the resource.
Shared/exclusive locks are frequently implemented using a simple count of the number of readers. The count is increased every time a new reader accesses the shared resource, and decremented when the reader relinquishes access. A writer may only access the resource when the reader count is at zero. This is because it is important that reading processes always view the most up-to-date information.
This method however, presents a number of problems. If one of the readers terminates abnormally, then it can be very difficult to adjust the count. If the count is not decremented properly then this can result in a writer waiting indefinitely for a process that is no longer accessing the resource.
Another problem relates to prioritising access to the resource. For example, if a resource already has one or more readers, should a writer or another reader be granted access when the current owner relinquishes access? With the above method, the choice depends upon whichever process gets there first. This can mean, for example, that a high priority writer is waiting unnecessarily on a low priority reader.
Both the above problems stem from the fact that insufficient information can be recorded about the readers. The dynamic nature of the number of readers, means that recording information is tricky. This method is therefore inefficient and lacks recoverability.
An alternative is to maintain a list of readers in a complex chain (linked list) structure. This solution can record appropriate information about each reader (such as a thread id and priority information) and is also recoverable. If, for example, a writer has been waiting for an exclusive lock on a resource for an excessively long a period of time, then the reader list can be traversed in order to check that the thread ids listed are still actively accessing the resource.
Unfortunately there is a significant performance overhead associated with the upkeep of such a structure. The number of readers in the list varies dynamically and thus storage allocation can become a problem. Further, it is necessary to lock the whole or a part of the structure before making a change to it. Deleting a reader also typically requires additional serialisation.
Accordingly, the invention provides a method for controlling access by a plurality of concurrently operating processes to a resource, said method comprising the steps of: allocating an area of storage and defining a pre-determined number of storage slots therein; responsive to a request by one of said processes for shared access to said resource, determining whether to allocate shared access, and if so, allocating said requesting process shared access, said step of allocating shared access comprising: acquiring one of said storage slots; and wherein said method further comprises: responsive to a request by one of said processes for exclusive access to said resource, determining whether to allocate exclusive access, and if so allocating said requesting process exclusive access, said step of allocating exclusive access comprising: acquiring all of said storage slots.
It should also be noted that although the terms multi-processing system and process are used throughout, this should also be taken to encompass threads which may run under the control of a process. Threads within one process may compete for access to a resource with threads from another process. However, threads within the same process may also compete for access to a resource. The invention is preferably aimed at controlling access to a resource in both such situations.
According to one embodiment, the step of determining whether shared access is to be allocated comprises selecting a storage slot and determining whether that storage slot is owned by another process (i.e. has been acquired by another process). Responsive to the slot not being owned by another process, the selected storage slot is acquired.
Alternatively, the step of determining whether shared access is to be allocated, comprises checking whether any one of a set of storage slots is unallocated and assuming that one is, an unallocated slot is acquired and shared access is allocated. The set of storage slots may comprise a part of the storage area, the whole storage area (i.e. slots 0 to n) or indeed, more than one pass of the storage area may be completed (e.g. 2n).
According to one embodiment, each process has at least one thread having a unique thread id. Each thread id is preferably unique not only within a process, but across all processes having access to the resource. A process indicates ownership of a storage slot by associating the thread id of the thread requesting access to the resource with the storage slot. (Ownership of a storage slot is exclusive and may not therefore be shared with another process.) A process also has priority information associated therewith.
In one embodiment, this priority information is used when allocating a process with shared access. Responsive to determining that a first storage slot is owned by another process, an action is performed based on the priority of the requesting process. If the requesting process has a low priority then the requesting process waits for the selected storage slot to be relinquished by the owning process and acquires the selected slot once this has occurred. If the requesting process has a high priority then storage slots continue to be selected until an unallocated storage slot is found and this unallocated slot is then acquired. Preferably no more than a predetermined number of storage slots are selected, and responsive to none of said selected storage slots being available, the requesting process waits for the last of the selected slots to be relinquished by an owning process. Once this last slot has been relinquished it is then acquired by the process requesting shared access.
According to one embodiment, an input queue is associated with at least one of the storage slots. When allocating shared access to the resource, if processes are queued on a selected storage slot, another storage slot is selected (e.g. either an unallocated slot or one without an associated queue). According to one embodiment, processes are queued according to their priority information. This may be used, for example, to move a high priority process to the head of a queue. This requires careful control to ensure that low priority requests do not wait indefinitely for access to the resource.
According to one embodiment, a process requesting shared access and having a low priority selects a storage slot from a first part of the storage area, whilst a process having a high priority selects a storage slot from a second part of the storage area. This ensures that low priority requests are pitted against one another and likewise with the high priority requests. A high priority request should not therefore, be forced to wait on a low priority request.
According to one embodiment, if none of the storage slots are available in the second part of the storage area, an unallocated storage slot is acquired in the first part of the storage area. Preferably this is not a regular occurrence since otherwise it is likely that low priority requests will have trouble gaining access to the resource.
According to one embodiment, in order to acquire all of the storage slots (i.e. to allocate exclusive access) each storage slot is selected. Responsive to a selected storage slot not being owned by another process, that storage slot is acquired. Responsive to a selected storage slot being owned by another process, the process requesting exclusive access waits until the storage slot is relinquished and then acquires the relinquished slot. Note, the storage slots may be selected sequentially or in some other order. Further this method of acquiring all of the storage slots may be used, for example, by a low priority process.
Alternatively, in order to acquire all of the storage slots (i.e. to allocate exclusive access), each storage slot not owned by another process (i.e. unallocated) is acquired on at least a first pass of the storage area. Subsequently each remaining slot (if there are any) is waited upon until it is relinquished and then that relinquished slot is acquired. Note, this method of acquiring all of the storage slots may be used, for example, by a high priority process.
In another embodiment, a process requesting exclusive access is informed as and when each allocated slot is relinquished and responsive to a slot being relinquished, the process acquires the relinquished slot. This continues until all slots have been acquired by the requesting process. In one embodiment there is a queue of processes requesting exclusive access and a process is only removed from the queue once it has acquired all slots in the storage area and thus access to the resource.
In one embodiment, each time a process requesting shared access acquires a storage slot, the position of that storage slot is recorded. Responsive to that process no longer requiring shared access to the resource, the slot denoting said process"" shared access is relinquished using said recorded position to locate the storage slot.
In another embodiment, a storage slot is selected and it is determined whether a thread id associated with a thread requesting that said shared access be relinquished matches a thread id associated with the selected storage slot. Responsive to a match, the selected storage slot is relinquished. Otherwise storage slots are selected until a match is achieved. Selection of storage slots may be sequential or otherwise.
In one embodiment one of a first part and a second part of the storage area are searched for the storage slot denoting said process"" shared access. For example, if the first part of the storage array is used by low priority requests and the second part by high priority requests, then a high priority request attempting to relinquish a storage slot will only search the second part of the storage area, and vice versa.
In one embodiment, responsive to a process no longer requiring exclusive access to the resource, access to all of said storage slots is relinquished.
According to another aspect, the invention provides a computer program product comprising computer program code recorded on a computer readable recording medium, which when executed on a computer, performs the method described above.
In a further aspect, the invention provides an apparatus having a storage, for controlling access by a plurality of concurrently operating processes to a resource, said apparatus comprising: means for defining a predetermined number of slots within said storage; means, responsive to a request by one of said processes for shared access to said resource, for determining whether to allocate shared access; and means, responsive to a determination that shared access is to be allocated, for allocating said requesting process shared access, said means for allocating shared access comprising: means for acquiring one of said storage slots; and wherein said apparatus further comprises: means, responsive to a request by one of said processes for exclusive access to said resource, for determining whether to allocate exclusive access; and means, responsive to a determination that exclusive access is to be allocated, for allocating said requesting process exclusive access, said means for allocating exclusive access comprising: means for acquiring all of said storage slots.
Whilst the present inventions does limit number of concurrent readers that are permitted to access a resource, it is beneficial to have this upper limit. This is because it is possible to accurately record information about the process(es) accessing a resource. Storage space can be pre-allocated and there is little overhead associated with managing the storage area.
The size of the storage area is preferably determined in accordance with the requirements of the system in which the invention is implemented. In other words, the storage area is preferably large enough to accommodate the typical number of processes concurrently requiring shared access to the resource. According to one embodiment the size of this area may be updated if the system""s requirements change or if the current setup is found not to be as efficient as first thought.